#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
typedef struct Node {
    int h, key;
    struct Node *lchild, *rchild;
} Node;

Node __NIL;
#define NIL (&__NIL)

__attribute__((constructor))
void init_NIL() {
    NIL->h = 0;
    NIL->key = -1;
    NIL->lchild = NIL->rchild = NIL;
    return ;
}

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->h = 1;
    p->key = key;
    p->lchild = p->rchild = NIL;
    return p;
}

void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}

void update_height(Node *root) {
    root->h = max(root->lchild->h, root->rchild->h) + 1;
}

Node *left_rotate(Node *root) {
    printf("left rotate : %d\n", root->key);
    Node *tmp = root->rchild;
    root->rchild = tmp->lchild;
    tmp->lchild = root;
    update_height(root);
    update_height(tmp);
    return tmp;
}

Node *right_rotate(Node *root) {
    printf("right rotate : %d\n", root->key);
    Node *tmp = root->lchild;
    root->lchild = tmp->rchild;
    tmp->rchild = root;
    update_height(root);
    update_height(tmp);
    return tmp;
}

const char *maintain_str[] = {"", "LL", "LR", "RL", "RR"};

Node *maintain(Node *root) {
    if (abs(root->lchild->h - root->rchild->h) <= 1) return root;
    int maintain_type = 0;
    if (root->lchild->h > root->rchild->h) {
        if (root->lchild->rchild->h > root->lchild->lchild->h) {
            root->lchild = left_rotate(root->lchild);
            maintain_type = 2;
        } else {
            maintain_type = 1;
        }
        root = right_rotate(root);
    } else {
        if (root->rchild->lchild->h > root->rchild->rchild->h) {
            root->rchild = right_rotate(root->lchild);
            maintain_type = 3;
        } else {
            maintain_type = 4;
        }
        root = left_rotate(root);
    }
    printf("AVL Maintain : %s\n", maintain_str[maintain_type]);
    return root;
}

Node *insert(Node *root, int key) {
    if (root == NIL) return getNewNode(key);
    if (key == root->key) return root;
    if (key < root->key) root->lchild = insert(root->lchild, key);
    else root->rchild = insert(root->rchild, key);
    update_height(root);
    return maintain(root);
}

Node *erase(Node *root, int key) {
    if (root == NIL) return NIL;
    if (key < root->key) root->lchild = erase(root->lchild, key);
    else if (key > root->key) root->rchild = erase(root->rchild, key);
    else {
        if (root->lchild == NIL || root->rchild == NIL) {
            Node *tmp = root->lchild == NIL ? root->rchild : root->lchild;
            free(root);
            return tmp;
        } else {
            Node *tmp = root->lchild;
            while (tmp->rchild != NIL) tmp = tmp->rchild;
            root->key = tmp->key;
            root->lchild = erase(root->lchild, tmp->key);
        }
    }
    update_height(root);
    return maintain(root);
}

void output(Node *root) {
    if (root == NIL) return ;
    printf("(%d(%d) | %d, %d)\n", root->key, root->h, root->lchild->key, root->rchild->key);
    output(root->lchild);
    output(root->rchild);
    return ;
}

Node *rand_insert(Node *root) {
    int val = rand() % 100;
    printf("\ninsert %d to avl tree : \n", val);
    root = insert(root, val);
    output(root);
    return root;
}

int main() {
    srand(time(0));
    int n;
    scanf("%d", &n);
    Node *root = NIL;
    for (int i = 0; i < n; i++) {
        root = rand_insert(root);
    }
    clear(root);
    return 0;
}